package uestc.lj.basic.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化和反序列化二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code11_SerializeAndReconstructTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}

	}

	/**
	 * 依据先序遍历序列化二叉树
	 *
	 * @param head
	 * @return
	 */
	public static String serializeByPre(Node head) {
		if (head == null) {
			return "#_";
		}
		String res = head.value + "_";
		res += serializeByPre(head.left);
		res += serializeByPre(head.right);
		return res;
	}

	public static Node reconstructTreeByPreString(String preStr) {
		String[] values = preStr.split("_");
		Queue<String> queue = new LinkedList<>();
		for (String value : values) {
			queue.add(value);
		}
		return reconPreOrder(queue);
	}

	private static Node reconPreOrder(Queue<String> queue) {
		String value = queue.poll();
		if ("#".equals(value)) {
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.left = reconPreOrder(queue);
		head.right = reconPreOrder(queue);
		return head;
	}
}